from typing import *


class Solution:

    def closedIsland(self, grid: List[List[int]]) -> int:

        class UnionFind():

            def __init__(self, size: int) -> None:
                self.p = [i for i in range(size)]
                self.cnts = [1] * size
                self.size = size
                self.value = [0] * size
                self.water = [False] * size
                self.ans = size

            def set_value(self, x, y, n, val):
                self.value[self.index(x, y, n)] = val

            def find(self, a):
                if self.p[a] != a:
                    self.p[a] = self.find(self.p[a])
                return self.p[a]

            def union(self, a: int, b: int):
                A, B = self.find(a), self.find(b)
                if A != B:
                    self.p[B] = A
                    self.cnts[A] += self.cnts[B]
                    self.cnts[B] = 0
                    self.size -= 1
                    self.ans -= 1
                    if not self.water[A] and self.water[B]:
                        self.ans -= 1
                    self.water[A] = (self.water[A] or self.water[B])

            def isSameSet(self, a: int, b: int) -> bool:
                return self.find(a) == self.find(b)

            def index(self, x, y, n):
                return x * n + y

            def merge(self, x, y, n):
                id = self.index(x, y, n)
                idl = self.index(x, y - 1, n)
                idu = self.index(x - 1, y, n)
                if y > 0 and self.value[id] == self.value[idl]:
                    self.union(id, idl)
                if x > 0 and self.value[id] == self.value[idu]:
                    self.union(id, idu)

        array = grid
        m, n = len(array), len(array[0])

        uf = UnionFind(m * n)
        for i in range(m):
            for j in range(n):
                if i == 0 or j == 0 or i == m - 1 or j == n - 1 or grid[i][
                        j] == 1:
                    uf.water[uf.index(i, j, n)] = True
                uf.set_value(i, j, n, array[i][j])
                uf.merge(i, j, n)

        s = set()
        for i in range(m):
            for j in range(n):
                if not uf.water[uf.find(uf.index(i, j, n))]:
                    s.add(uf.find(uf.index(i, j, n)))
        return len(s)


so = Solution()
print(
    so.closedIsland(grid=[[1, 1, 1, 1, 1, 1, 1, 0], [1, 0, 0, 0, 0, 1, 1, 0],
                          [1, 0, 1, 0, 1, 1, 1, 0], [1, 0, 0, 0, 0, 1, 0, 1],
                          [1, 1, 1, 1, 1, 1, 1, 0]]))

array = [[0, 1, 1, 1, 0], [1, 0, 1, 0, 1], [1, 0, 1, 0, 1], [1, 0, 0, 0, 1],
         [0, 1, 1, 1, 0]]
for row in array:
    print(row)
print(so.closedIsland(array))

array = [[0, 0, 1, 1, 0, 1, 0, 0, 1, 0], [1, 1, 0, 1, 1, 0, 1, 1, 1, 0],
         [1, 0, 1, 1, 1, 0, 0, 1, 1, 0], [0, 1, 1, 0, 0, 0, 0, 1, 0, 1],
         [0, 0, 0, 0, 0, 0, 1, 1, 1, 0], [0, 1, 0, 1, 0, 1, 0, 1, 1, 1],
         [1, 0, 1, 0, 1, 1, 0, 0, 0, 1], [1, 1, 1, 1, 1, 1, 0, 0, 0, 0],
         [1, 1, 1, 0, 0, 1, 0, 1, 0, 1], [1, 1, 1, 0, 1, 1, 0, 1, 1, 0]]
for row in array:
    print(row)
print(so.closedIsland(array))